Barcodes are commonly used to provide electronic identification of physical artifacts. They are printed on different types of documents to store information for later retrieval, such as supermarket receipts, air tickets, product packages, etc. Moreover, they can also function as control keys in multimedia systems.
It is thus important for automated systems to be able to detect the locations of barcodes in a document image in order to decode them to retrieve the data. Some commercial products can decode barcodes accurately. However, the typical practice for using barcodes in documents is to surround barcodes by white space to insure detection. Efficiently locating barcodes in high resolution scans is still an open issue. Previous research in this field mainly focuses on detecting barcodes in the pixel domain, which is computationally expensive for page size, high resolution scanned images.
Several approaches are commonly used for barcode detection. In one approach, the stripes of a barcode are first detected by applying connected component analysis, and then the barcode regions are determined by grouping the connect components. For example, one proposal to detect the barcode region includes grouping connected components into barcode blocks in a down-sampled and background-removed image. For more information, see U.S. Pat. No. 4,948,955, entitled “Barcode Location Determination”, issued on Aug. 14, 1990. A system that applied connected component analysis to detect both horizontal and vertical barcodes, conditioned on the specifications of the shapes of the stripes and the gaps between adjacent stripes was described in U.S. patent application Ser. No. 09/522,978, entitled “Method of Reading Barcode and Barcode Reading System,” filed Mar. 10, 2000 (U.S. Publication No. 2002/0074405A1), published on Jun. 20, 2002).
There are also barcode detection techniques that use grids to divide the document image into small cells. A certain feature for each cell is calculated to determine whether it belongs to a barcode region or not, and finally the cells are grouped together to determine the barcode region. Different features can be applied. For example, one technique uses the matching between adjacent rows/columns in three directions. For more information, see EPO Patent No. 0894311B1, entitled “Omnidirectional Barcode Locator,” issued on Jun. 10, 1999. Another technique uses the black-white transitions along the grids. For more information, see EPO Application No 1416421A1, entitled “Barcode Detection System and Corresponding Method.” Still another technique detects some parallel stripe patterns by scanning each cell in various directions. For more information, see U.S. patent application Ser. No. 09/847,484, entitled “Fast Barcode Search,” filed May 2, 2001 (U.S. Publication No. 2002/0162889A1, published on Nov. 7, 2002).
Other methods make use of histograms. For example, one method detects a certain histogram pattern in segments of a particular type of barcode, the POSTNET code. But since it only captured the characteristics of POSTNET code as described in U.S. Pat. No. 5,073,954, entitled “Bar Code Location and Recognition Processing System,” issued on Dec. 17, 1991, the usage of this method is limited. A method to detect barcodes that match a set of off-line trained sample barcodes was introduce in U.S. patent application Ser. No. 09/877,581, entitled “Automatically Extracting Graphical Bar Codes,” filed on Jun. 7, 2001 (Publication No. 2002/0196979A1, published on Dec. 26, 2002). Candidate barcode regions are selected by applying a matched filter along several preselected directions in windows centered at different locations. The geometric verification on the deskewed candidate barcode region is implemented by projecting the barcode onto orthogonal axes and threshold the histograms.
All these previous approaches for detecting barcodes work in the pixel domain and are computationally expensive on large images.
JPEG 2000 is a standardized wavelet-based compression method to represent digital images in a coherent code-stream and file format. For more information, see “Information technology—JPEG 2000 image coding standard—part 1: core coding system”, ISO/IEC 15444-1. Compared to other compression standards, JPEG 2000 has advantages such as access to different resolutions and different parts of an image. In a JPEG 2000 codestream, compressed blocks of wavelet coefficients and header data are included. The wavelet coefficients provide detailed high frequency information of the image along different directions and on different scales. Each wavelet subband of each level is partitioned into local groups of typically 32×32 or 64×64 coefficients called code-blocks. Each code-block is independently encoded. Main header data contains the high level structural description of the entire image and coding parameters used. The packet headers contain information such as number of bits allocated to each code-block, the number of zero bit-planes and the coding passes for the purpose of decoding. JPEG 2000 header information has previously been used to find regions of interest for purposes such as comparing documents.